\section{($\epsilon$-) Optimal strategies for the two-move lag}
In this section, all the ($\epsilon$-)optimal strategies for the original two-move lag problem are introduced. 
\label{Strategy2Lag}. Finally, the implementation of the computer simulation is briefly explained.

\subsection{Optimal strategy for the ship}
\label{Strategy2LagShip}

The ship can ensure to be hit with a probability $\leq v_n$ by playing the strategy which minimizes the probability to be at a certain point after two steps:
In the very first move it can randomly choose one of the $n+1$ reachable nodes. Then at every step it moves forwards with probability $p$ and backwards with probability 
$(1-np)$. Remember that a $n$-restricted graph has $n+1$ neighbours, hence $n$ forward neigbours and one backward neighbour. The following equations show the probabilities where the ship will be after two moves:
\begin{itemize}
 \item Probability to be back at the starting point after the first two steps $P(N_{S})=\sum_{i=1}^{n+1} {\frac{1}{n+1}}(1-np)= 1-np$
 \item Probability to be two steps away from the starting point after the first two steps $P(N_{S2})=\frac{p}{n+1}$
 \item Probability to be at the same point after two steps $P(N_0)=\sum_{i=1}^{n}p(1-np)+(1-np)(1-np)=1-np $
  \item Probability to be at any of the $n^2$ points two steps away, not passing the node just visited $P(N_2)=p^2$
\item Probability to be two steps away, passing the node just visited $P(N_{-2})=(1-np)p$
\end{itemize}
The minimum of the maximum for the three functions $p^2$, $(1-np)p$ and $1-np$ is given for
\begin{equation}
 p=\frac{\sqrt{n^2+4}-n}{2};
\end{equation}
and results in the following value:
\begin{equation}
 v_n=p^2=1-np=\frac{n^2+4-n\sqrt{n^2+4}}{2}
\end{equation}

Since the two probabilities where the ship can be after the very first two moves ($1-np$ and $\frac{p}{n+1}$) are also $\le v_n$, the highest probability where the ship can be after two 
steps is $v_n$. This means that this is an optimal strategy for the ship for the two-move lag.






\subsection{$\epsilon$-Optimal strategy for the bomber}
\label{Strategy2LagBomber}

For the bomber, probability $w$ is the lower bound of hitting the ship. The bomber's strategy is illustrated in figure \ref{StrategyBomber} for the one-restricted graph of figure \ref{GraphN2}. 
The same idea holds for a $n$-restricted graph.

\begin{figure}[h]
\begin{center}
 \includegraphics[width=3in]{Bilder/2restrictedGraphBomberStrategy.png}
\caption{Idea of the bomber's strategy in one-restricted graph}
\label{StrategyBomber}
\end{center}
\end{figure}


In the beginning the ship is at node \textit{0} and the bomber bombs this place with probability $p_0$. Then the ship moves from node \textit{0} to node \textit{1}. 
The bomb is placed on the nodes \textit{1} or \textit{3} with probability $p_1$. Under the condition that the ship moves to node \textit{2} it will be hit with probability $p_1$ in the next move. 
So $\omega=\frac{p_1}{p_0+(n^2+1)*p_1}$ (= probability to hit the ship if it does not return to the starting point, under the condition that the bomb is dropped at time zero or one). 
But if the ship returns to the starting place it will be hit with probability $p_0$, and since $w$ it the lower bound it has to be ensured that  $\frac{p_0}{p_0+(n^2+1)*p_1} \ge \frac{p_1}{p_0+(n^2+1)*p_1}
=\omega$. 
This condition can not be guaranteed and the procedure is repeated. The nodes \textit{0} and \textit{-2} are bombed with probability $p_2$. Now again, if the 
ship moves from node \textit{0} to node \textit{-1} $w=\frac{p_0+p_2}{p_0+(n^2+1)*(p_1+p2)}$, but if it returns to node \textit{1} it has to be ensured that  $\frac{p_0+p_1}{p_0+(n^2+1)*(p_1+p2)}\ge \omega$. 
The procedure is repeated untill the following conditions are true: 
\begin{equation}
 \omega = \frac{p_0+p_1+\dots+p_{k-2}+p_k}{p_0+(n^2+1)(p_1+p_2+\dots+p_k)} 
\label{Omega1}
\end{equation}

\begin{equation}
 \omega \le \frac{p_0+p_1+\dots+p_{k-1}}{p_0+(n^2+1)(p_1+p_2+\dots+p_k)} 
\label{biggerOmega}
\end{equation}
where $k$ is the first occurrence where $p_{k-1}\ge p_k$.\\
$p_j$, with $j=1,\dots,k$ is the probability that the bomb is dropped at time $j$, which means that the ship has switched $j$ times between two points. It is calculated as 
\begin{equation}
 p_j=C_1(\frac{\alpha+\sqrt{\alpha^2-4\alpha}}{2})^j+C_2(\frac{\alpha-\sqrt{\alpha^2-4\alpha}}{2})^j
\end{equation}
with
\begin{equation}
\alpha=(1-(n^2+1)\omega)^{-1},
\end{equation}

\begin{equation}
 2C_1=1-\frac{(n^2-1)\alpha+2}{(n^2+1)\sqrt{\alpha^2-4\alpha}}
\end{equation}
and 
\begin{equation}
 C_1+C_2=1.
\end{equation}
The target, where the bomber drops the 
bomb, is randomly chosen between the node where the ship is at the current moment and the $n^2$ nodes which can be reached in two steps, not reversing the ship's traveling direction. \cite{Ferguson} 
An example for the two-move lag would be that the ship walks the path \textit{0-1-0}, then the target is node \textit{0} or node 
\textit{-2}.

Since the equations \ref{Omega1} and \ref{biggerOmega} can only be satisfied if $\omega < v_n$, the bomber's strategy is an $\epsilon$-optimal strategy. 


\subsection{Implementation discrete state model}
\label{Implementation}
This subsection is about the implementation of our computer simulation of the bomber-battleship problem. 
The original problem is about an infinite $n$-restricted graph. But only a part of this graph is relevant to the ship and the bomber. The implementation only generates the relevant part of this graph which depends on the time-lag and $n$. 
Both of these parameters influence the possible places for the bomber to bomb. The relevant part that is generated goes from the current place of the ship to the positions time-lag places away and everything in between.
The main idea of this method is that the ship always stays in the center position $1$. 
If the ship moves in one direction it stays at this position $1$ and only if the bomb is dropped the position of this bomb in the graph will 
change depending on the move of the ship. 
If, after the ship has moved, the bomb would fall outside of the graph, the bomb will disappear, because then it is not possible anymore that this bomb will hit the ship. 

\begin{figure}[h]
\begin{center}
 \includegraphics[width=2.5in]{Bilder/shipsGraph}
\caption{Implemented graph for $n=2$, two-move lag}
\label{ShipsGraph}
\end{center}
\end{figure}



Figure \ref{ShipsGraph} clarifies the idea. It shows the graph for $n=2$ and the two-move lag.
The nodes \textit{7,8,9} and \textit{10} mark the $n^2$ nodes, reachable by moving two times forwards. The nodes $5$ and $6$ are the $n$ nodes 
the ship can reach after two time steps if it goes back and then forwards. But the implementation is such that the ship always stays at node $1$ and the bomb comes closer or moves away, depending on the ship's movements.



